package LeetCode.exercise;
import java.util.Arrays;

public class LC_1089 {
    public static void main(String[] args) {
        int[] arr = {1,0,2,3,0,4,5,0};
        arr = duplicateZeros(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static int[] duplicateZeros(int[] arr) {
        //先找出最后一个被复写的元素,cur指向该元素,dest指向最后面的元素
        int cur = 0, dest = -1, n = arr.length;
        //通过双指针找出最后一个被复写的元素,cur指向元素为 0,dest+2,
        //否则+1,当dest>=n-1,此时cur所指的元素即为最后一个被复写的元素
        for (; cur < n; cur++) {
            if (arr[cur] != 0) { // cur指向元素不为0
                dest++;     //      dest+1
            } else {             // cur指向元素为0
                dest += 2;  //      dest+2
            }
            if (dest >= n - 1) {  //当dest>=n-1,说明cur指向元素就是所找元素,满足退出条件
                if (dest == n) {  //如果dest=n,说明越界
                    arr[dest - 1] = 0; //将最后一个元素置为0
                    dest -= 2; //dest向前移动2的元素位置
                    cur--;     //cur向前移动一个元素位置
                }
                break;
            }
        }
        //双指针  从后往前遍历 cur检查是否为0, dest替换元素
        for (; cur >= 0; cur--) {
            if (arr[cur] != 0) { //cur指向元素不为0
                arr[dest--] = arr[cur]; //将cur指向元素赋给dest指向元素,然后双指针分别向前移动1
            } else {
                arr[dest--] = 0; //cur指向元素为0
                arr[dest--] = 0; //将dest指向元素和前一个元素置为0,dest向前移动2,cur向前移动1
            }
        }
        return arr;
    }
}
